/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: YKH
 * Date: 2022-06-24
 * Time: 20:07
 */
//构建一棵二叉搜索树
public class BinarySearchTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    TreeNode root;

    //插入
    public boolean insert( int val) {
        if( root == null) {
            root = new TreeNode(val);
            return true;
        }
        TreeNode cur = root;
        TreeNode parents = null;
        while( cur! = null) {
            if( val > cur.val) {
                parents = cur;
                cur = cur.right;
            } else if( val < cur.val) {
                parents = cur;
                cur = cur.left;
            } else {
                return false;
            }
        }
        //走到这里cur为空 ,判断将值插入到 parent的左边还是右边
        if( val >   parents.val) {
            parents.right = new TreeNode(val);
        } else {
            parents.left = new TreeNode(val);
        }
        return true;
    }
    //中序遍历
    public void inorder( TreeNode root) {
        if(root == null) {
            return ;
        }
        inorder( root.left);
        System.out.println( root.val + " ");
        inorder(root.right);
    }
}
